package com.ljx.GetNumber;

import java.util.PriorityQueue;

/**
 * @author 李加喜
 * @Package com.ljx.GetNumber
 * @date 2021-12-14 16:24
 */
public class MedianFinder {
    public static void main(String[] args) {

    }

    /**
     * 小顶堆  顶小
     */
    private PriorityQueue<Integer> large;
    /**
     * 大顶堆 顶大
     */
    private PriorityQueue<Integer> small;
    public MedianFinder() {
        large=new PriorityQueue<>();
        small=new PriorityQueue<Integer>((a,b)->{
            return b-a;
        });
    }
    /**
     * 不仅要维护large和small的元素个数之差不超过 1，
     * 还要维护large堆的堆顶元素要大于等于small堆的堆顶元素
     * small大  la小
     */
    public void addNum(int num) {
        if (small.size()>=large.size()){
            small.offer(num);
            large.offer(small.poll());
        }else {
            large.offer(num);
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        // 如果元素不一样  那么那个多堆的堆顶就是中位数
        if (large.size()>small.size()){
            return large.peek();
        }else if (large.size()<small.size()){
            return small.peek();
        }
        //如果一样多  堆顶相加去中间数
        return (large.peek()+small.peek())/2.0;
    }
}
